//给你一个字符串 word 和一个 非负 整数 k。 
//
// 返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。
// 
//
// 
//
// 示例 1： 
//
// 
// 输入：word = "aeioqq", k = 1 
// 
//
// 输出：0 
//
// 解释： 
//
// 不存在包含所有元音字母的子字符串。 
//
// 示例 2： 
//
// 
// 输入：word = "aeiou", k = 0 
// 
//
// 输出：1 
//
// 解释： 
//
// 唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。 
//
// 示例 3： 
//
// 
// 输入：word = "ieaouqqieaouqq", k = 1 
// 
//
// 输出：3 
//
// 解释： 
//
// 包含所有元音字母并且恰好含有一个辅音字母的子字符串有： 
//
// 
// word[0..5]，即 "ieaouq"。 
// word[6..11]，即 "qieaou"。 
// word[7..12]，即 "ieaouq"。 
// 
//
// 
//
// 提示： 
//
// 
// 5 <= word.length <= 250 
// word 仅由小写英文字母组成。 
// 0 <= k <= word.length - 5 
// 
//
// Related Topics 哈希表 字符串 滑动窗口 👍 14 👎 0


package LeetCode.editor.cn;


import java.util.*;

/**
 * @author ldltd
 * @date 2025-03-12 09:41:09
 * @description 3305.元音辅音字符串计数 I
 
 */
 
public class CountOfSubstringsContainingEveryVowelAndKConsonantsI {
    public static void main(String[] args) {
    //测试代码
    CountOfSubstringsContainingEveryVowelAndKConsonantsI fun = new CountOfSubstringsContainingEveryVowelAndKConsonantsI();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u');
    //令count(K)表示每个元音字母至少出现一次，并且至少包含k哥辅音字母的子字符串的总数
    //则答案为count(K)-count(k+1）
    //因为count(K)包含了所有大于等于k的值，因此需要k+1的减去k，得到恰好k个值的
    //对于区间i,j，枚举左右端点，不断右移j直到元音至少出现一次，且包含至少k个辅音字母或者j到达右端
    //右端点固定后，如果区间合格，那么左端i的子字符串满足的数目为n-j+1。

    public int count(String word, int m) {
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
        int n = word.length(), consonants = 0;//辅音数量
        int res = 0;
        Map<Character, Integer> occur = new HashMap<>();//元音计数
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j < n && (consonants < m || occur.size() < 5)) {
                char ch = word.charAt(j);
                if (vowels.contains(ch)) {
                    occur.put(ch, occur.getOrDefault(ch, 0) + 1);
                } else {
                    consonants++;
                }
                j++;
            }
            if (consonants >= m && occur.size() == 5) {
                res += n - j + 1;
            }
            char left = word.charAt(i);
            if (vowels.contains(left)) {
                occur.put(left, occur.get(left) - 1);
                if (occur.get(left) == 0) {
                    occur.remove(left);
                }
            } else {
                consonants--;
            }
        }
        return res;
    }

    public int countOfSubstrings(String word, int k) {
        return count(word, k) - count(word, k + 1);
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
